import java.util.Arrays;
import java.util.TreeSet;

/**
 * 二分查找
 * 不同于线性查找，二分查找必须是有序数组
 *
 * @Author: wanqian
 * @Date: 2021/2/3 13:57
 */
public class BinarySearch {

    public static int[] arr = {53, 3, 542, 748, 14, 214, 23, 77, 4, 5, 118, 45, 96, 1, 14, 14};

    public static void main(String[] args) {
        //需要对数组进行排序
        Arrays.sort(arr);
        System.out.println(String.format("排序后数组为： %s", Arrays.toString(arr)));
        int target = 14;
        int i = binarySearch(arr, 0, arr.length - 1, target);
//        TreeSet<Integer> targets = binarySearch2(arr, 0, arr.length - 1, target);

        if (i != -1) {
//            for (int i : targets) {
            System.out.println(String.format("找到目标arr[%d] = %d", i, target));
//            }
        } else {
            System.out.println("未找到目标");
        }
    }

    /**
     * 二分查找
     *
     * @param arr
     * @param left
     * @param right
     * @param target
     * @return
     */
    public static int binarySearch(int[] arr, int left, int right, int target) {

        //当递归到最后只剩一个数时，仍不是我们的目标数
        //下次递归则left > right，结束查找
        if (left > right) {
            return -1;
        }

        System.out.println("查找数组" + left + "到" + right);
        //找到左右指针中间的位置
        int mid = (right + left) / 2;
        if (arr[mid] > target) {
            //中间值大于目标值，继续找左半边
            return binarySearch(arr, left, mid - 1, target);
        } else if (arr[mid] < target) {
            //中间值小于目标值，继续找右半边
            return binarySearch(arr, mid + 1, right, target);
        } else {
            //等于则直接结束查找，返回结果
            return mid;
        }

    }

    /**
     * 二分查找（存在多个相同的目标值）
     *
     * @param arr
     * @param left
     * @param right
     * @param target
     * @return
     */
    public static TreeSet<Integer> binarySearch2(int[] arr, int left, int right, int target) {
        //当递归到最后只剩一个数时，仍不是我们的目标数
        //下次递归则left > right，结束查找
        if (left > right) {
            return new TreeSet<>();
        }

        System.out.println("查找数组" + left + "到" + right);
        //找到左右指针中间的位置
        int mid = (right + left) / 2;
        if (target < arr[mid]) {
            //目标值小于中间值，继续找左半边
            return binarySearch2(arr, left, mid - 1, target);
        } else if (target > arr[mid]) {
            //目标值大于中间值，继续找右半边
            return binarySearch2(arr, mid + 1, right, target);
        } else {
            //由于是有序数组，所以相同的目标数一定是相邻的
            TreeSet<Integer> targets = new TreeSet<>();
            targets.add(mid);
            //向左继续查找
            int i = mid - 1;
            while (arr[i] == target) {
                targets.add(i--);
            }
            //向右继续查找
            int j = mid + 1;
            while (arr[j] == target) {
                targets.add(j++);
            }
            return targets;
        }
    }
}
